package lcr;

public class Test0064 {
    public static void main(String[] args) {
        MagicDictionary magicDictionary = new MagicDictionary();
        magicDictionary.buildDict(new String[]{"hello","leetcode"});
        System.out.println(magicDictionary.search("hhllo"));
    }
}

class MagicDictionary {
    Dict dict;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        dict= new Dict();
    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            dict.insert(s.toCharArray(),0);
        }
    }

    public boolean search(String searchWord) {
        return dict.search(searchWord.toCharArray(),0,false);
    }


    class Dict{
        Dict[] next;
        boolean isWord;

        public Dict(){
            isWord = false;
        }

        public void insert(char[] chars, int index){
            if (next == null) next = new Dict[26];
            Dict dict = next[chars[index] - 'a'];
            if (dict == null) {
                dict = new Dict();
                next[chars[index] - 'a'] = dict;
            }

            if (index == chars.length - 1){
                dict.isWord = true;
            }else {
                dict.insert(chars, index + 1);
            }
        }

        public boolean search(char[] chars, int index,boolean isChange){
            if (isChange){
                if (index==chars.length) return isWord;
                Dict dict;
                if (next == null|| (dict = next[chars[index] - 'a']) ==null) return false;
                return dict.search(chars,index+1,true);
            }else {
                if (next==null||index==chars.length) return false;
                char c = chars[index];

                for (int i = 0; i < 26; i++) {
                    Dict dict1 = next[i];
                    if (i != c - 'a'&& dict1 !=null) {
                        boolean search = dict1.search(chars, index + 1, true);
                        if (search) return true;
                    }
                }
                return next[c - 'a'] != null? next[c - 'a'].search(chars, index + 1, false):false;
            }
        }

    }
}

